package com.leetcode.algorithm.y22.m06;

/**
 * 931. 下降路径最小和
 * 
 * https://leetcode.cn/problems/minimum-falling-path-sum/
 * 
 * @author jie.deng
 *
 */
class Question0931Solution01 {

	public int minFallingPathSum(int[][] matrix) {
		int rows = matrix.length;
		int cols = matrix[0].length;

		// DP状态定义+滚动数组
		int[][] dp = new int[2][cols];
		// 状态初始化
		for (int col = 0; col < cols; col++) {
			dp[0][col] = matrix[0][col];
		}
		// 状态转移方程
		for (int row = 1; row < rows; row++) {
			int preRow = row - 1 & 1;
			int curRow = row & 1;
			for (int col = 0; col < cols; col++) {
				int minFallingPathSum = dp[preRow][col];
				if (col > 0 && dp[preRow][col - 1] < minFallingPathSum) {
					minFallingPathSum = dp[preRow][col - 1];
				}
				if (col < cols - 1 && dp[preRow][col + 1] < minFallingPathSum) {
					minFallingPathSum = dp[preRow][col + 1];
				}
				dp[curRow][col] = matrix[row][col] + minFallingPathSum;
			}
		}

		int lastRow = rows - 1 & 1;
		int minFallingPathSum = dp[lastRow][0];
		for (int col = 1; col < cols; col++) {
			if (dp[lastRow][col] < minFallingPathSum) {
				minFallingPathSum = dp[lastRow][col];
			}
		}
		return minFallingPathSum;
	}

}